/*
** 1007.c
** 
** Made by (seakage2h)
** Login   <seakage2h@seakage2h-ubuntu>
** 
** Started on  Fri Sep  5 16:06:21 2008 seakage2h
** Last update Sun May 12 01:17:25 2002 Speed Blue
*/

/* #include "1007.h" */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
/* #include <ctype.h> */


typedef struct
{
     int entropy;		/* the smaller, the more ordered. */
     
     char* dna_group;		/* the pointer to the start position
				 * of a DNA sequence */
     
     int acg[3];		/* the accumulated amount of ACG,
				 * acg[0]:A, acg[1]:C, acg[2]:T */
} dna_stat;

int dna_stat_comp(const void* dna1, const void* dna2)
{
     dna_stat** arg1 = (dna_stat**)dna1;
     dna_stat** arg2 = (dna_stat**)dna2;
     
     if ((*arg1)->entropy < (*arg2)->entropy)
	  return 1;
     else if ((*arg1)->entropy == (*arg2)->entropy)
	  return 0;
     else return -1;
     
}

int main()
{
     char *dna, *tmp;		/* dna: point to all DNA datas
				 * tmp: point to target DNA group temporarily*/
     
     dna_stat **sorted_group;	/* the array store the start position pointer
				 * to DNA sequences states */
     dna_stat *tmpg;		/* used in initialization */
     
     int length, group;		/* store length of a DNA group, and
				 * group number */
     int i, j;
     char c;

     scanf("%d%d", &length, &group);

     /* store the input DNAs */
     dna = (char*) malloc(sizeof(char) * (length * group + 1)); /* for '\0' */
     /* store the internal states of the DNA sequences */
     sorted_group = (dna_stat**) malloc(sizeof(dna_stat*) * group);
     for(i = 0, tmp = dna; i < group; i++, tmp += length){
	  sorted_group[i] = (dna_stat*)malloc(sizeof(dna_stat));
	  sorted_group[i]->entropy = 0;
	  sorted_group[i]->dna_group = tmp;
	  sorted_group[i]->acg[0] = 0;
	  sorted_group[i]->acg[1] = 0;
	  sorted_group[i]->acg[2] = 0;	  
     }

/*      /\* GET 1: using getchar *\/ */
/*      for(i = 0, tmp = dna; i < group; i++, tmp = tmp + length){ */
/* 	  while(isspace(c = getchar())); /\* no space *\/ */
/* 	  tmp[0] = c; */
/* 	  for(j = 1; j < length; j++) */
/* 	       tmp[j] = getchar(); */
/*      } */

     /* GET 2: using scanf */
     for (i = 0, tmp = dna; i < group; i++, tmp += length)
	  scanf("%s",tmp);

     /* STATISTICS */
     for(i = 0; i < group; i++)
     /* calculate ACG, then revise entropy */
	  for(j = length - 1; j >= 0; j--){
	       tmp = sorted_group[i]->dna_group;
	       switch(tmp[j]){
	       case 'A':
		    sorted_group[i]->acg[0]++;
		    break;
	       case 'C':
		    sorted_group[i]->acg[1]++;
		    sorted_group[i]->entropy -= sorted_group[i]->acg[0];
		    break;
	       case 'G':
		    sorted_group[i]->acg[2]++;
		    sorted_group[i]->entropy -= sorted_group[i]->acg[0] +\
			 sorted_group[i]->acg[1];
		    break;
	       case 'T':
		    sorted_group[i]->entropy -= sorted_group[i]->acg[0] +\
			 sorted_group[i]->acg[1] + sorted_group[i]->acg[2];
	       }
	  }

     /* SORT: use qsort() to help us */
     qsort(sorted_group, group, sizeof(dna_stat*), dna_stat_comp);
     
/*      /\* DEBUG output: all stored DNA sequences *\/ */
/*      for(i = 0, tmp = dna; i < group; i++, tmp = tmp + length){ */
/* 	  for(j = 0; j < length; j++) */
/* 	       putchar(tmp[j]); */
/* 	  putchar('\n'); */
/*      } */
/*      /\* DEBUG output: all entropies *\/ */
/*      for(i = 0; i < group; i++) */
/* 	  printf("The entropy of group %d is: %d\n", i + 1, */
/* 		 sorted_group[i]->entropy); */

     /* FINAL output */
     for(i = 0; i < group; i++){
	  for(j = 0, tmp = sorted_group[i]->dna_group; j < length; j++)
	       putchar(tmp[j]);
	  putchar('\n');
     }
     
     return 0;
     
}
